

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class MapSum {
    Map<String,Integer> map;
    public MapSum() {
        map=new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key,val);
    }

    public int sum(String prefix) {
        int sum=0;
        for(String s : map.keySet()){
            if(s.startsWith(prefix)){
                sum+=map.get(s);
            }
        }
        return sum;
    }
}













class MapSum1 {
    Map<String,Integer> map;
    /** Initialize your data structure here. */
    public MapSum1() {
        map=new HashMap<>();
    }

    public void insert(String key, int val) {
        map.put(key,val);
    }

    public int sum(String prefix) {
        int sum=0;
        for(String s : map.keySet()){
            if(s.startsWith(prefix)){
                sum+=map.get(s);
            }
        }
        return sum;
    }
}


public class project {
    List<List<Integer>> list=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Deque<Integer> deque=new ArrayDeque<>();
        Arrays.sort(candidates);
        dfs(candidates,target,0,candidates.length,deque);
        return list;
    }
    public void dfs(int[] arr,int key,int start,int end,Deque<Integer> deque){
        if(key<0){
            return ;
        }
        if(key==0){
            list.add(new LinkedList<>(deque));
            return;
        }
        for(int i=start;i<end;i++){
            if(i>start&&arr[i]==arr[i-1]){
                continue;
            }
            deque.addLast(arr[i]);
            dfs(arr,key-arr[i],i+1,end,deque);
            deque.removeLast();
        }
    }











//    List<List<Integer>> list=new LinkedList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        Arrays.sort(candidates);
//        Deque<Integer> deque=new ArrayDeque<>();
//        dfs(candidates,target,deque,0,candidates.length);
//        return list;
//    }
//    public void dfs(int[] arr,int key,Deque<Integer> deque,int start,int len){
//        if(key<0){
//            return ;
//        }
//        if(key==0){
//            list.add(new LinkedList<>(deque));
//            return;
//        }
//        for(int i=start;i<len;i++){
//            if(i>start&&arr[i]==arr[i-1]){
//                continue;
//            }
//            deque.addLast(arr[i]);
//            dfs(arr,key-arr[i],deque,i,len);
//            deque.removeLast();
//        }
//    }












    public int longestCommonSubsequence(String text1, String text2) {
        int row=text1.length();
        int col=text2.length();
        int[][] arr=new int[row+1][col+1];
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    arr[i][j]=arr[i-1][j-1]+1;
                }else{
                    arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
                }
            }
        }
        return arr[row][col];
    }












    public int longestCommonSubsequence1(String text1, String text2) {
        int row=text1.length();
        int col=text2.length();
        int[][] arr=new int[row+1][col+1];
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    arr[i][j]=arr[i-1][j-1]+1;
                }else{
                    arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
                }
            }
        }
        return arr[row][col];
    }











    public int singleNonDuplicate(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(mid%2==1){
                mid--;
            }
            if(nums[mid]==nums[mid+1]){
                left+=2;
            }else{
                right=mid;
            }
        }
        return nums[left];
    }













    public int singleNonDuplicate1(int[] nums) {
        int left=0;
        int right=nums.length-1;
        while(left<right){
            int mid=left+(right/2);
            if(mid%2==1){
                mid++;
            }
            if(nums[mid]==nums[mid+1]){
                left=mid+2;
            }else{
                right=mid;
            }
        }
        return nums[left];
    }









    public int maxProfit(int[] prices) {
        int max=0;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<prices.length;i++){
            min=Math.min(min,prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        return max<0?0:max;
    }














    public List<Integer> largestValues(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                int max=queue.peek().val;
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    max=Math.max(max,tmp.val);
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
                list.add(max);
            }
        }
        return list;
    }














    public List<Integer> largestValues1(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        Queue<TreeNode> queue=new ArrayDeque<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                int max=queue.peek().val;
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    max=Math.max(max,tmp.val);
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
                list.add(max);
            }
        }
        return list;
    }
}
